#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <ctime>
#include <cassert>

#include <sys/types.h>
#include <sys/stat.h>
#include <errno.h>


#include <sys/time.h>
using namespace std;

typedef int int4;
typedef char byte1;
typedef timeval tv;


#define Assert
#define MAX_KEY_NUM	22
#define MAX_LIST_LEN	330000
#define BLOCK_SIZE	1024

#define swap(a, b) \
	if(a != b) \
	{ a ^= b;	b ^= a; a ^= b; }

#define swap2(t, a, b) \
	{ t _ = a; a = b; b = _; }



const char fidx1[] = "/home/wanghc/workspace/sogou_data/idx1.correct.ref.centos.dat";
const char finput[] = "/home/wanghc/workspace/sogou_data/input.correct.sorted.centos.dat";
const char finvt[] = "/home/wanghc/workspace/sogou_data/invt_idx.centos.dat";


// get file size in bytes
int get_file_size(const char *path)
{
	struct stat buf;
	stat(path, &buf);
	return buf.st_size;
}

// read file content to memory
// as int array
/*void* read_file(const char *path)
{
	int size = get_file_size(path);
	byte1* ptr = (byte1*)new int4[size / sizeof(int4) * sizeof(byte1)];
	//byte1* ptr = new byte1[size];
	
	ifstream fin;
	
	fin.open(path, ios::in | ios::binary);
		int t = size / BLOCK_SIZE * BLOCK_SIZE;
		
		for(int i = 0; i < t; i += BLOCK_SIZE)
			fin.read((char *) (ptr + i), BLOCK_SIZE);
			
		fin.read((char *) (ptr + size - size % BLOCK_SIZE), 
			size % BLOCK_SIZE);
			
		int read_num = fin.tellg();
	fin.close();
	
	assert(read_num == size);

	return (void*)ptr;
}*/


void* load_file(const char *path)
{
	struct stat buf;
	stat(path, &buf);

	FILE* fp = fopen(path, "rb");
	byte1* ptr = (byte1*)malloc(buf.st_size);
	int count = 0, bytes;
	byte1* p = (byte1*)ptr;

	while((bytes = fread(p + count, 1, 1024, fp)) > 0)
	{
		count += bytes;
	}
	
	fclose(fp);
	return ptr;
}

inline int binary_search(int4 tag, int4* arr, int l, int h)
{
	int m;
	while(l <= h)
	{
		m = (l + h) / 2;
		if(tag > arr[m])
			l = m + 1;
		else if(tag < arr[m])
			h = m - 1;
		else
			return m;
	}
	
	return -l - 1;
}

// insertion sort
/*inline void insert_sort(int len, int4* keys)
{
	int k;
	for(int i = 0; i < len - 1; i++)
	{
		k = i;
		
		for(j = i + 1; j < len; j++)
		{
			if(idx1[arr[k] * 2] < idx1[arr[j] * 2])
			{
				k = j;
			}
		}
		
		if(i != k)
		{
			swap(arr[i], arr[k]);
		}
	}
}*/



tv get_time()
{
	tv t;
	gettimeofday(&t, NULL);
	return t;
}

tv time_diff(tv t1, tv t2)
{
	t1.tv_sec = t1.tv_sec - t2.tv_sec;
	t1.tv_usec = t1.tv_usec - t2.tv_usec;

	if(t1.tv_sec * t1.tv_usec < 0)
	{
		if(t1.tv_sec < 0)
		{
			t1.tv_sec++;
			t1.tv_usec -= 1000000;
		}
		else
		{
			t1.tv_sec--;
			t1.tv_usec += 1000000;
		}
	}

	return t1;
}

tv time_add(tv t1, tv t2)
{
	t1.tv_sec = t1.tv_sec + t2.tv_sec;
	t1.tv_usec = t1.tv_usec + t2.tv_usec;

	if(t1.tv_usec >= 1000000)
	{
		t1.tv_usec -= 1000000;
		t1.tv_sec++;
	}
	return t1;
}

int is_ordered(int len, int4* arr)
{
	int m = -1;
	for(int i = 0; i < len; i++)
	{
		if(m >= arr[i]) return 0;
			m = arr[i];
	}
	return 1;
}




inline int fw_search(const int tag, int4 *arr, int s, int e)
{
	#ifdef Assert
	assert(tag > arr[s]);
	assert(s <= e);
	#endif
	//if(tag == arr[s]) return s;
	//else if(tag < arr[s]) return -s -1;

	int diff = e - s + 1;
	int m = 4;
	int pos = 2;
	
	while(pos < diff)
	{
		if(tag == arr[pos + s])
			return pos + s;
		else if(tag < arr[pos + s])
			return binary_search(tag, arr, s + pos / 2, s + pos - 1);
		else
		{
			m <<= 1;
			pos = m - 2;
		}
	}
	
	return binary_search(tag, arr, s + pos / 2, e);
}

inline int fw_search2(const int tag, int4 *arr, int len)
{
	if(tag == arr[0]) return 0;
	else if(tag < arr[0]) return -1;
	
	int m = 4;
	int pos = 2;
	
	while(pos < len)
	{
		if(tag == arr[pos])
			return pos;
		else if(tag < arr[pos])
			return binary_search(tag, arr, pos / 2, pos - 1);
		else
		{
			m <<= 1;
			pos = m - 2;
		}
	}
	
	return binary_search(tag, arr, pos / 2, len - 1);
}

inline int bw_search(const int tag, int4* arr, int s, int e)
{
	int pos = 2;
	
	while(pos <= e)
	{
		if(tag == arr[e - pos])
			return e - pos;
		else if(tag > arr[e - pos])
			return binary_search(tag, arr, e - pos + 1, e - pos / 2);
		else
			pos = (pos << 1) + 2;
	}
	
	return binary_search(tag, arr, s, e - pos / 2);
}

inline int bw_search(const int tag, int* arr, int len)
{
	int p = 2;
	len--;
	
	while(p <= len)
	{
		if(tag == arr[len - p])
			return len - p;
		else if(tag > arr[len - p])
			return binary_search(tag, arr, len - p + 1, len - p / 2);
		else
			p = p * 2 + 2;
	}
	
	return binary_search(tag, arr, 0, len - p / 2);
}


void show_list(int4* arr, int len)
{
	int cols = 8;
	int show_all = 0;
	
	for(int i = 0; i < len; i++)
	{
		if(i != 0 && i % cols == 0)
			cout<<endl;
		
		if(show_all == 0 && i != 0 && i % (cols * 20) == 0)
		{
			while(1)
			{
				cout<<"(a)ll/(e)nd/(N)ext page?"<<endl;
				char c = getchar();
				if(c >= 'A' && c <= 'Z')
					c = c + 'a' - 'A';
				
				if(c == 'a')
				{
					show_all = 1;
					break;
				}
				else if(c == 'e')
					return;
				else if(c == '\n' || c == 'n')
					break;
			}
		}
		
		if(i % cols == 0)
			cout<<setw(8)<<(i / cols)<<":";
			
		cout<<setw(10)<<arr[i];
	}
	cout<<endl;
}